package perfectMenu;

import java.util.LinkedList;
import java.util.Stack;

public class Solution {
    int ans = -1;
    public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
        // 饱腹感>=limit 美味感的最大值
        // 多种料理的组合
        // 回溯
        // 判断当前组合能否满足条件---饱腹感>=limit并且食材足够
        trackBack(materials,cookbooks,0,new LinkedList<>(),attribute,limit);
        return ans;
    }
    private void trackBack(int[] materials, int[][] cookbooks, int start, LinkedList<Integer> cooks, int[][] attribute, int limit) {
        if(checkEnough(limit,cooks,attribute)&&checkMaterials(materials,cookbooks,cooks)){
            ans = Math.max(ans,getAttribute(attribute,cooks));
        }
        for (int i = start; i < cookbooks.length; i++) {
            cooks.addLast(i);
            trackBack(materials,cookbooks,i+1,cooks,attribute,limit);
            cooks.removeLast();
        }
    }
    private int getAttribute(int[][] attribute,LinkedList<Integer> cooks) {
        int s = 0;
        for (int cook: cooks) {
            s+=attribute[cook][0];
        }
        return s;
    }
    private boolean checkEnough(int limit,LinkedList<Integer> cooks,int[][] arrtribute) {
        int sum = 0;
        for (int cook: cooks) {
            sum+=arrtribute[cook][1];
        }
        return sum>=limit;
    }

    private boolean checkMaterials(int[] materials,int[][] cookbooks,LinkedList<Integer> cooks) {
        int[] map = new int[5];
        for (int cook: cooks) {
            for (int j = 0; j < cookbooks[cook].length; j++) {
                map[j] += cookbooks[cook][j];
            }
        }
        for (int i = 0; i < materials.length; i++) {
            if(map[i]>materials[i]){
                return false;
            }
        }
        return true;
    }
}
